package binaryTree;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

//判断平衡二叉树
public class LeetCode_110 {

    //节点结构
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);

        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        TreeNode lca = lowestCommonAncestor(root, root.left.left, root.right);
        System.out.println(lca.val);


    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return solution_2(root,p,q);
    }

    /**
     * 解法1：非递归解决
     * @param root   根节点
     * @return TreeNode：lca
     */
    private TreeNode solution_1(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        HashSet<TreeNode> set = new HashSet<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        //1. 层次遍历，同时利用map记录父节点信息
        map.put(root, null);
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left!= null) {
                map.put(node.left, node);
                queue.add(node.left);
            }
            if (node.right!= null){
                map.put(node.right, node);
                queue.add(node.right);
            }
        }
        //2. 利用set存储p的所有父节点
        while (p!= null) {
            set.add(p);
            p = map.get(p);
        }
        //3. 遍历q的所有父节点，判断是否在set中
        while (q!= null) {
            if (set.contains(q)) {
                return q;
            }
            q = map.get(q);
        }
        return null;
    }

    /**
     * 解法2：递归解决
     * @param root   根节点
     * @return TreeNode：lca
     */
    private TreeNode solution_2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q){
            return root;
        }
        TreeNode left = solution_2(root.left, p, q);
        TreeNode right = solution_2(root.right, p, q);
        if(left != null && right != null){
            return root;
        }else if(left != null && right == null){
            return left;
        }else if(left == null && right != null){
            return right;
        }else{
            return null;
        }
    }


}
